//二分查找的变种
public class BinarySearch2 {
    private BinarySearch2() {
    }

    // 如果数组中没有，则返回数组中最大的索引的值加1
    // >target的最小值的索引
    public static <E extends Comparable<E>> int upper(E[] data, E target) {
        //arr[l,r)
        int l = 0, r = data.length;
        while (l < r) {
            int mid = l + (r - l) / 2;
            //target大于mid的情况
            if (data[mid].compareTo(target) <= 0) {
                l = mid + 1;
            } else {
                //target小于等于mid的情况
                r = mid;
            }
        }
        return l;
    }

    // >target，返回最小值索引
    // =target，返回最大索引
    public static <E extends Comparable<E>> int ceil(E[] data, E target) {
        //>target的最小值的索引
        int u = upper(data, target);
        if (u - 1 >= 0 && data[u - 1].compareTo(target) == 0) {
            return u - 1;
        }
        return u;

    }

    // >=target的最小索引
    public static <E extends Comparable<E>> int lower_ceil(E[] data, E target) {
        int l = 0, r = data.length;
        //[l,r]
        while (l < r) {
            int mid = (l + r) / 2;
            //target小于mid的情况
            if (data[mid].compareTo(target) > 0) {
                l = mid + 1;
            } else {
                //target大于的等于mid的情况
                r = mid;
            }
        }
        return l;
    }

    public static void main(String[] args) {
        Integer[] arr = {1, 1, 3, 3, 5, 5};
        for (int i = 0; i <= 6; i++) {
            System.out.print(upper(arr, i) + " ");
        }
    }


}
